FIG. 1 depicts a schematic diagram of a packet-based telecommunications network in the prior art, which enables host computers that have access to the network (e.g., Alice, Bob, Charlie and Denise) to communicate. As is typical of packet-based networks in the prior art, network 101 comprises a plurality of geographically distributed packet switches that are interconnected by duplex communication links in the topology of a graph. Each packet switch in network 101 is schematically depicted by a circle that encompasses a unique whole number, from 1 to 15, and each duplex communication link is depicted by a dotted line that interconnects two circles. As shown in FIG. 1, Alice, Bob, Charlie and Denise each have access to network 101 via packet switches #8, #13, #10 and #3, respectively.
When one host with access to network 101 desires to send data to another host with access to the network, the transmitting host parses the information into a set of packets, which are serially presented to the network. Depending on the nature of the data and the convention that the respective hosts have agreed to for communication, the sequential order in which the set of packets are presented to the network might also be the order in which the packets are preferably delivered by the network. In other words, in some cases it may be advantageous for network 101 to preserve the sequential order of the packets, and in other cases it may be inconsequential.
As known in the prior art, there are two fundamentally different techniques that network 101 can use to route packets from the transmitting host to the destination host: (1) connectionless (i.e., datagram) service, which does not preserve the sequential order of the packets, and (2) connection-oriented (i.e., virtual-circuit) service, which does preserve the sequential order of the packets. Both datagram service and virtual service have their respective advantages and disadvantages, which will be described in detail below. The book Computer Networks, 2nd Ed., by Andrew S. Tanenbaum, Prentice-Hall, Inc., provides an excellent introduction to packet-based telecommunications and is hereby incorporated by reference as if set forth in its entirety.
An understanding of datagram service is facilitated by analogy to the postal system. In the same manner that the postal system handles each piece of mail separately, and without regard to another piece of mail, networks that provide datagram service handle each packet separately. To use the postal system, a postal patron must put the complete address of the addressee on each piece of mail, even though the same patron may mail multiple pieces of mail to the same addressee at the same time and from the same place. Similarly, a host that uses a network that provides datagram service must include the complete address of the ultimate destination of the packet with each packet, even though a single host may transmit a thousand packets to the same destination.
With regard to the postal system, the requirement that each piece of mail contain a complete postal address is further necessitated by the fact that each piece of mail can take alternative routes to the same ultimate destination. And because the length of each route can vary, and so too the speed through each route, two pieces of mail that were mailed concurrently can arrive at different times. It is also further the case that two pieces of mail, mailed sequentially from the same place and to the same ultimate destination can arrive out of order. Analogously, a datagram network can transport packets via different routes such that a set of packets that were presented to the network in one sequential order can be delivered by the network in a different order.
To reduce the need for redundant hardware (e.g., power supplies, memory, telephone poles, etc.), multiple elemental networks, such as those depicted in FIGS. 2-5, are usually fabricated as a composite physical network, as shown in FIG. 1. For example, a duplex communication channel or network is, in reality, a composite of two simplex communication channels or elemental networks. For the purposes of this specification, an elemental network is defined as one or more integrated simplex communication channels that are capable of delivering packets to a destination, which destination may be a packet switch or host computer.
Both FIGS. 2 and 3 depict examples of elemental networks, in accordance with connectionless techniques well known in the prior art. FIG. 2 depicts an elemental network that transports packets from packet switch #3 to packet switch #10 and FIG. 3 depicts a elemental network that transports packets from packet switch #13 to packet switch #3.
Each packet switch in a network that provides datagram service contains a router table that indicates where it should route packets that arrive at it. Table 1 depicts a typical router table that might be associated with packet switch #3 in FIG. 1 (when network 101 provides only datagram service). When a packet arrives at a packet switch, the packet switch looks at the address in the packet's addressee field and uses that address as an index into the router table to determine to which neighboring packet switch the packet should be routed. For example, the neighboring packet switches of packet switch #3 are packet switches #1, #2, #5 and #7. In this manner, packets are handed from one packet switch to another, in bucket brigade fashion, until they reach their final destination.
TABLE 1 ______________________________________ A Typical Router Table in a Packet Switch in a Datagram Network (Packet Switch #3) ______________________________________ ##STR1## ______________________________________
When, for example, a packet enters packet switch #3 with address 10 in the packet's addressee field, the packet switch learns from Table 1 that the preference is to send the packet to packet switch #7. When, however, packet switch #3 determines that the communication link to packet switch #7 is congested, unavailable, or for any other reason, not favorable, the router table indicates that the second choice is to send the packet to packet switch #5. For similar reasons, more alternative choices may also be given. Note that when a packet arrives with address 3 in the packet's addressee field, meaning that the packet has arrived at its destination in the network, the router table indicates that the packet is to be passed to the appropriate host that is associated with the packet switch.
Network control in datagram networks (i.e., the process of dealing with network congestion, packet switch and communication link failure, network administration, network maintenance, etc.) is performed by each packet switch in a distributed fashion and is accomplished by providing each packet switch with alternative destinations to which packets can be routed.
In contrast to datagram service, there exists virtual-circuit service. An understanding of virtual-circuit service is facilitated by analogy to plain, old telephone service. When a person desires to talk to another via the telephone, the calling party "dials" the number of the called party, which is a request to the telephone network to establish a private circuit from the calling party to the called party. Once the circuit is established, the calling party and called party can exchange information, without further interaction with the telephone network. When the parties' conversation is completed, they "hang-up," which indicates to the telephone network that the conversation is completed and that the circuit can be torn-down.
Analogously, when Denise desires to send packets to Charlie, and network 101 provides virtual-circuit service, Denise must first indicate to network 101 that she desires to be connected with Charlie. Network 101 then uses two elemental networks, one from Denise to Charlie and the second from Charlie to Denise, to establish a virtual-circuit. FIGS. 4 and 5 depict examples of elemental networks from Denise to Charlie.
Once the virtual-circuit between Denise and Charlie is established, all Denise need do to send packets to Charlie is address them with the indicia of the virtual-circuit associated with them both. The network will route the packets along the elemental network and deliver them to Charlie. Analogously, all Charlie need do to send packets to Denise is address them with the indicia of the virtual-circuit associated with them both. The network will route the packets along the elemental network and deliver them to Denise. And because all of the packets follow the same path, the sequential order of the packets is preserved. When Denise and Charlie are finished communicating, either merely indicates to the network that it can tear-down the virtual-circuit.
Although neither Charlie nor Denise is required to address each packet with the address of the ultimate packet switch in the elemental network, each packet is required to carry an identifier of the virtual-circuit that it is associated with. Each packet switch in a network that provides virtual-circuit service contains a router table that guides the packet switch where to route each packet that arrives at it. Table 2 depicts a typical router table that might be associated with packet switch #3 when it provides virtual-circuit service.
TABLE 2 ______________________________________ A Typical Router Table in a Virtual Circuit Network ______________________________________ ##STR2## ______________________________________
A packet switch that provides virtual-circuit service must perform a different task than a packet switch that provides datagram service. When, for example, a packet enters packet switch #3 on virtual-channel #3 from packet switch #2, the packet switch uses the router table in Table 2 not only to learn which packet switch the packet is to be routed through, but also with which virtual-channel identifier ("VCI"). Therefore, each packet switch must overwrite, in each packet's VCI field, the name of the outgoing virtual-channel into which the packet is put. In this example, the packet switch outputs the packet to packet switch #7 and overwrites the VCI of 3 with a 2. Virtual-circuit networks deal with network congestion and network failures by setting-up new virtual-circuits in less congested, working parts of the network. In other words, entries are usually made into the router tables in virtual-circuit networks at call set-up, in contrast with datagram networks where in the entries are made into the router tables before call establishment.
There are two principal advantages of datagram networks over virtual-circuit networks: (1) datagram networks do not require connection set-up and tear-down, which can be prohibitively slow or expensive depending on the application, and (2) the packet switches in datagram networks are usually less expensive to build because they do not have to overwrite the VCI field of each packet passing through the packet switch. The principal advantages of virtual-circuit networks over datagram networks is that virtual-circuit networks preserve the sequential order of packets, which is essential for certain applications, and that network control is handled on an ad hoc basis. There is, however, a need for a packet-based telecommunications network architecture that preserves the sequential order of packets, and yet avoids the disadvantages associated with virtual-circuit networks.